package LeetCode;

public class LC_154_FindMinimuminRotatedSortedArrayII {

    public static void main(String[] args) {

    }

    static class Solution {
        public int findMin(int[] num) {
            return findMin(num, 0, num.length - 1);
        }

        private int findMin(int[] num, int left, int right) {
            if (right == left)
                return num[left];
            if (right == left + 1)
                return Math.min(num[left], num[right]);
            int middle = (right - left) / 2 + left;
            if (num[right] > num[left])
                return num[left];
            else if (num[right] == num[left])
                return findMin(num, left + 1, right);
            else if (num[middle] >= num[left])
                return findMin(num, middle, right);
            else
                return findMin(num, left, middle);
        }
    }

    static class Solution_2 {
        public int findMin(int[] nums) {
            int i = 0;
            int j = nums.length - 1;
            while (i <= j) {
                while (nums[i] == nums[j] && i != j)
                    i++;
                if (nums[i] <= nums[j])
                    return nums[i];
                int m = (i + j) / 2;
                if (nums[m] >= nums[i])
                    i = m + 1;
                else
                    j = m;
            }
            return -1;
        }
    }

}